package main

import (
	"container/list"
	"fmt"
	"time"
)

//树的前序遍历

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归
func preorder1(root *TreeNode) (res []int) {
	var pre func(*TreeNode)
	pre = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val) //中（前序 前就是第一步实现）
		pre(node.Left)              //左
		pre(node.Right)             //右
	}
	pre(root)
	return
}

// Preorder2
//非递归（迭代）借助栈
//对于前序遍历（中左右）
//压栈顺序：右左中 因为栈是先进后出的
func Preorder2(root *TreeNode) (res []int) {
	if root == nil {
		return
	}
	var stack = list.New() //新建一个双向链表
	//PushBack 将值为v的新元素插入链表的最后一个位置 返回生产的新元素
	stack.PushBack(root.Right)  //压入右节点
	stack.PushBack(root.Left)   //压入左节点
	res = append(res, root.Val) //输出中间值
	for stack.Len() > 0 {       //只要栈里面有元素
		e := stack.Back()           //弹出链表最后一个元素并将其存储到e中
		stack.Remove(e)             //删除链表中的元素e 并返回e.Value
		node := e.Value.(*TreeNode) //e是Element类型 其值为e.Value 由于Value为接口 要类型断言
		if node == nil {
			continue //进行下次for循环
		}
		res = append(res, node.Val) //将栈弹出的元素输出
		stack.PushBack(node.Right)  //压入右节点
		stack.PushBack(node.Left)   //压入左节点
	}
	return res
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 3}
	A.Left.Left = &TreeNode{Val: 4}
	A.Left.Right = &TreeNode{Val: 5}
	A.Right.Left = &TreeNode{Val: 6}

	start1 := time.Now()
	fmt.Println(preorder1(A))
	end1 := time.Since(start1)
	fmt.Println("递归时间：", end1)

	start2 := time.Now()
	fmt.Println(Preorder2(A))
	end2 := time.Since(start2)
	fmt.Println("迭代时间：", end2)
}
